<?php

class EditDistanceCalculator {
	
	private $distances;
	private $path;
	private $len1;
	private $len2;
	/**
	 * Pseudocode from: http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
	 * 
	 * @param string $a
	 * @param string $b
	 * @return integer 
	 */
	function calculate($a, $b, $withTranspositionStep = false) {
		$this->a = $a;
		$this->b = $b;
		$first = str_split($this->a);
		$second = str_split($this->b);
		$this->len1 = count($first);		// or strlen
		$this->len2 = count($second);
		$distances = $this->constructDistancesMatrix($this->len1, $this->len2);
		
		if ($this->len1 == 0) {
			
			return $this->len2;
		} else if ($this->len2 == 0) {
			
			return $this->len1;
		}
		
		for ($i = 0; $i <= $this->len1; $i++) {
			$this->distances[$i][0] = $i;
		}
		
		for ($j = 0; $j <= $this->len2; $j++) {
			$this->distances[0][$j] = $j;
		}
		
		for ($i = 1; $i <= $this->len1; $i++) {
			for ($j = 1; $j <= $this->len2; $j++) {
				$cost = 1;
				if ($first[$i-1] == $second[$j-1]) {
					$cost = 0;
				}

				/* Levehrstein distance */
				$this->distances[$i][$j] = min(array(
					$this->distances[$i-1][$j] + 1,		// Deletion
					$this->distances[$i][$j-1] + 1,		// Insertion
					$this->distances[$i-1][$j-1] + $cost 	// Substitution
				));
				
				/* Damerau–Levenshtein distance */
				if ($withTranspositionStep) {
					if (
						$i > 1 &&
						$j > 1 &&
						$first[$i-1] == $second[$j-2] &&
						$first[$i-2] == $second[$j-1]	
					) {				
						$this->distances[$i][$j] = min(array (
							$this->distances[$i][$j],
							$this->distances[$i-2][$j-2] + $cost
						));
					}
				}
			}
		}
		
		$this->constructPath();
		return $this->distances[$this->len1][$this->len2];
	}
	
	function constructDistancesMatrix($len1, $len2) {
		$matrix = array();
		
		for ($i = 0; $i <= $len1; $i++) {
			$matrix[$i] = array();
			for ($j = 0; $j <= $len2; $j++) {
				$matrix[$i][$j] = -1;
			}
		}
		
		return $matrix;
	}
	
	public function constructPath() {
		for ($i = 0; $i <= $this->len1; $i++) {
			$this->path[$i] = array();
			for ($j = 0; $j <= $this->len2; $j++) {
				$this->path[$i][$j] = 0;
			}
		}
		
		$i = $this->len1;
		$j = $this->len2;
		
		$this->path[$i][$j] = 1;
		while ($i > 0 || $j > 0) {
			$minI = $i-1;
			$minJ = $j-1;
			$p1 = $this->distances[$i-1][$j];
			$p2 = $this->distances[$i][$j-1];
			$p3 = $this->distances[$i-1][$j-1];
			
			if ($p2 < $p3) {
				$minI = $i;
				$minJ = $j-1;
			}
			
			if ($p1 < $p2) {
				$minI = $i-1;
				$minJ = $j;
			}
			
			$i = $minI;
			$j = $minJ;
			
			$this->path[$i][$j] = 1;
		}
	}
	
	public function getDistances() {
		
		return $this->distances;
	}
	
	public function getPath() {
		
		return $this->path;
	}
}
